package com.wl2o2o.lanqiao.xzfourteen;

import java.util.Arrays;
import java.util.Scanner;

/** 
* @author : WLei224
* @date ：2023年2月16日 上午9:48:12 
* 
*/
public class SieveOfAs {
	/**
	 * 何为埃式筛法？就是将1-sqrt(n)范围内数字的倍数标记为非素数（合数），然后筛选出剩下的数就是素数
	 * @param args
	 */

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//输入一个数字，程序给出n以内的素数
		int n = scanner.nextInt();
		//声明一个n以内的boolean数组
		boolean[] isPrime = new boolean[n+1];
		Arrays.fill(isPrime, true);
		
		//埃式筛法
		for(int i = 2; i*i<=n; i++) {
			if(isPrime[i] == true)
				for(int j = 2; i*j <= n; j++) {
					isPrime[i*j] = false;
				}
		}
		
		//输出素数
		for(int x = 2; x <= n; x++) {
			if(isPrime[x] == true) System.out.println(x);
		}
		
	}

}
